import entity.TreeNode;

public class DeleteNodeInBST {
    /*
    * 450. 删除二叉搜索树中的节点
    * 给定一个二叉搜索树的根节点 root 和一个值 key，
    * 删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。
    * 返回二叉搜索树（有可能被更新）的根节点的引用。
    * 一般来说，删除节点可分为两个步骤：
    * 首先找到需要删除的节点；
    * 如果找到了，删除它。
    *
    * 节点数的范围 [0, 10^4].
    * -10^5 <= Node.val <= 10^5
    * 节点值唯一
    * root 是合法的二叉搜索树
    * -10^5 <= key <= 10^5

    * */
    public static void main(String[] args){

    }

    // 我的想法：
    // 1.找到要删除的节点
    // 2.删,存下原左儿和原右儿
    // 3.拆掉原左儿的右儿，用原右儿连
    // 4.把拆掉的右儿连到新右儿上
    // 5.父节点连接原左儿
    public TreeNode mySolution(TreeNode root, int key){
        if(root == null)
            return null;
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null && cur.val != key){  // 找
            parent = cur;
            if(cur.val > key)
                cur = cur.left;
            else
                cur = cur.right;
        }
        if(cur == null)     //没找到
            return root;

        //看看删的是不是叶子节点
        if(cur.left == null && cur.right == null){
            if(parent == null)
                return null;
            else {
                if (parent.val > key)
                    parent.left = null;
                else
                    parent.right = null;
            }
            return root;
        }
        if(cur.left != null && cur.right == null){
            if (parent == null)
                return cur.left;
            else {
                if(parent.val > key)
                    parent.left = cur.left;
                else
                    parent.right = cur.left;
                return root;
            }
        }
        if(cur.right != null && cur.left == null){
            if (parent == null)
                return cur.right;
            else {
                if(parent.val > key)
                    parent.left = cur.right;
                else
                    parent.right = cur.right;
                return root;
            }
        }

        // 需要拼接
        TreeNode lr = cur.left.right;    // 存左儿的右儿
        cur.left.right = cur.right;     // 连原右儿
        if(lr != null){
            TreeNode flag = cur.right;   // 拆掉的右儿连到新右儿上
            TreeNode pre = null;
            while (flag != null) {
                pre = flag;
                if (lr.val < flag.val)
                    flag = flag.left;
                else
                    flag = flag.right;
            }
            if(pre.val > lr.val)
                pre.left = lr;
            else
                pre.right = lr;
        }
        if(parent == null)
            return cur.left;
        else {
            if(parent.val > key)
                parent.left = cur.left;
            else
                parent.right = cur.left;
        }
        return root;
    }

    // 这代码长度，多少有点屎山的感觉了，一堆逻辑判断。
    // 还是来写感人的递归吧
    // 返回条件，空，没找到，或者返回拼接节点
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        if(root.val > key)
            root.left = deleteNode(root.left, key);
        else if(root.val < key)
            root.right = deleteNode(root.right, key);
        else {
            if(root.left == null && root.right == null)
                return null;
            if(root.left != null && root.right == null)
                return root.left;
            if(root.right != null && root.left == null)
                return root.right;
            // 把左儿子拼到右儿子上会方便很多
            TreeNode cur = root.right;
            while (cur.left != null)
                cur = cur.left;
            cur.left = root.left;
            return root.right;
        }
        return root;
    }
}
